package demo.practice.tree.depth;

import demo.practice.TreeNode;

public class P563 {

//    public int findTilt(TreeNode root) {
//
//    }



    /*public int findTilt(TreeNode root) {
        if(root==null)
            return 0;
        int po = Math.abs( count(root.left)-count(root.right));//当前节点的坡度
        return po+findTilt(root.right)+findTilt(root.left);
    }

    Map<TreeNode,Integer> map= new HashMap<>();
    public int count(TreeNode root){//节点值的总和
        if(root==null)
            return 0;
        if(map.get(root)!=null)
            return map.get(root);
        int count=root.val+ (root.left==null?0:count(root.left))+ (root.right==null?0:count(root.right));
        map.put(root,count);
        return root.val+ (root.left==null?0:count(root.left))+ (root.right==null?0:count(root.right));
    }*/


    public int findTilt(TreeNode root) {
        int[] count = new int[]{0, 0};
        findTilt(root,count);
        return count[1];
    }

    public void findTilt(TreeNode root, int[] count) {//count中存高度和 坡度两个维度

        if (root == null) {
            //当前节点为空，啥也不做
            return;
        }

        int[] countL = new int[]{0, 0};
        if (root.left != null) {
            findTilt(root.left, countL);
        }

        int[] countR = new int[]{0, 0};
        if (root.right != null) {
            findTilt(root.right, countR);
        }

        //count[0]记录数值和
        //count[1]记录坡度和
        count[0] += root.val + countL[0] + countR[0];
        count[1] += Math.abs(countL[0] - countR[0]) + countL[1]  + countR[1];

    }


}
